package com.leetcode.nc02;

import com.leetcode.entity.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 单链表
 * L0->L1->L2->...->Ln-1
 * 排序之后，显示：
 * L0->Ln-1->L1->Ln-2->L2->Ln-3->...
 * 解题思路：
 *      
 */
public class NC02 {
    public static void main(String[] args) throws Exception{
        System.out.println("请输入链表数据,数据以逗号分隔：");
        Scanner scanner = new Scanner(System.in);
        String content = scanner.next();

        String[] numStrs = content.split(",");

        // 定义链表头
        ListNode head = null, tail = null;
        for (String str : numStrs) {
            if (head == null) {
                head = tail = new ListNode(Integer.parseInt(str));
            }
            else {
                tail.next = new ListNode(Integer.parseInt(str));
                tail = tail.next;
            }
        }

        // 先把ListNode转成数组
        ListNode node = sort2(head);

        StringBuilder sb = new StringBuilder("");
        while (node != null) {
            sb.append(node.val + "->");
            node = node.next;
        }
        System.out.println(sb.toString());

    }

    /**
     * 方法1排序
     * 先将node进行遍历，组装成数组
     * 定义两个指针，头指针和尾指针，分别指向数组的头和尾
     * 从头部开始
     * @param node
     * @return
     */
    public static ListNode sort1(ListNode node) {
        List<ListNode> list = new ArrayList<>();
        do {
            list.add(node);
            node = node.next;
        } while (node != null);

        int i = 0, j = list.size() - 1;

        while (i < j) {
            // j是尾节点
            list.get(i).next = list.get(j);
            // 指针往下一个移动
            i++;
            if (i == j)
                break;
            list.get(j).next = list.get(i);
            j--;
        }

        list.get(i).next = null;

        // 取list第一个节点即可
        return list.get(0);
    }

    /**
     * 使用二分法寻找列表的中间节点
     * 然后以中间节点，将节点分成前后两端A,B
     * 将B进行倒排
     * A和B每个节点进行相连
     * slow指针   每次走一步
     * fast指针   每次走两步
     * @return
     */
    public static ListNode sort2(ListNode node) {
        ListNode slow = node, fast = node;
        // TODO fast的速度是slow的两倍
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // TODO 以slow.next为中间点，分为两个链表
        ListNode secondNode = slow.next;
        slow.next = null;

        // TODO 两个链表 node和secondNode
        // TODO 对secondNode进行反转
        ListNode hnode = reverse(secondNode);

        // TODO 合并node和secondNode
        ListNode headNode = node;
        while (hnode != null) {
            ListNode tmp = headNode.next;
            ListNode tmp2 = hnode.next;
            headNode.next = hnode;
            hnode.next = tmp;
            hnode = tmp2;
            headNode = tmp;
        }

        return node;
    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode tail = head;
        head = head.next;
        tail.next = null;

        while (head != null) {
            ListNode tmp = head.next;
            head.next = tail;
            tail = head;
            head = tmp;
        }

        // 返回头节点
        return tail;
    }
}
